# -*- coding: utf-8 -*-

# __date:       2021/7/11
# __author:     Yang Chao
# __function:   Longest Common Prefix 最长公共前缀


class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        """
        最长公共前缀不可能超过strs列表中某一个元素的长度，因此遍历strs[0]的长度，直接看代码
        :param strs:
        :return:
        """
        if not strs:
            return ""

        for i in range(len(strs[0])):
            for _str in strs:
                if len(_str) <= i or _str[i] != strs[0][i]:
                    return strs[0][:i]

        return strs[0]

    def longestCommonPrefix2(self, strs: List[str]) -> str:
        """
        动态规划求解问题：
            dp[i]代表前i+1个字符串的最大前缀串;
            如果第i+2个字符串不以dp[i]为前缀，就去掉dp[i]的最后一个字符再试一次
            都去完了那么dp[i+1]肯定就是空串了，也就等于这时候的dp[i]，因为dp[i]的每个字符已经被去完了
        :param strs:
        :return:
        """
        if not strs:
            return None

        dp = ["" for _ in range(len((strs)))]
        dp[0] = strs[0]
        for i in range(1, len(strs)):
            while not strs[i].startswith(dp[i - 1]):
                dp[i - 1] = dp[i - 1][:-1]
            dp[i] = dp[i - 1]  # 更新当前的dp[i]

        return dp[-1]